package dp;

import java.util.Arrays;

/**
 * leet-code(338): 比特位计数
 *
 * @author Ringo
 * @date 2021/9/27 22:35
 */
public class CountBits {

    public static void main(String[] args) {
        int n = 5;
        System.out.println(Arrays.toString(countBits1(n)));
        System.out.println(Arrays.toString(countBits2(n)));
    }


    /**
     * 调用 {@link Integer#bitCount(int)} API
     */
    public static int[] countBits1(int n) {
        int[] ans = new int[n + 1];
        for (int i = 0; i <= n; ++i) {
            ans[i] = Integer.bitCount(i);
        }
        return ans;
    }

    // 动态规划
    public static int[] countBits2(int n) {
        int[] bits = new int[n + 1];
        int highBit = 0;
        for (int i = 1; i <= n; ++i) {
            // i & (i - 1): 判断 i 是不是 2 的幂
            if ((i & (i - 1)) == 0)
                highBit = i;
            // 如果 i 是 2 的幂. bit[i] = 0 + 1 = 1
            // 如果 i 不是 2 的幂. 假如 i = 5, 这时 highBit = 4
            // bit[i] = bit[5 - 4] + 1 = 2
            // 本质就是 5 = 4 + 1. 4 的二进制只有一个1.
            // bits[1] 存的就是 1 的二进制有几个1
            bits[i] = bits[i - highBit] + 1;
        }
        return bits;
    }
}
